{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Non-decreasing Subarray From Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNonDecreasingLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造最长非递减子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong> 开始的整数数组 <code>nums1</code> 和 <code>nums2</code> ，长度均为 <code>n</code> 。</p>\n",
    "\n",
    "<p>让我们定义另一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组，<code>nums3</code> 。对于范围&nbsp;<code>[0, n - 1]</code> 的每个下标 <code>i</code> ，你可以将 <code>nums1[i]</code> 或 <code>nums2[i]</code> 的值赋给 <code>nums3[i]</code> 。</p>\n",
    "\n",
    "<p>你的任务是使用最优策略为 <code>nums3</code> 赋值，以最大化 <code>nums3</code> 中 <strong>最长非递减子数组</strong> 的长度。</p>\n",
    "\n",
    "<p>以整数形式表示并返回 <code>nums3</code> 中 <strong>最长非递减</strong> 子数组的长度。</p>\n",
    "\n",
    "<p><strong>注意：子数组</strong> 是数组中的一个连续非空元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [2,3,1], nums2 = [1,2,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>构造 nums3 的方法之一是： \n",
    "nums3 = [nums1[0], nums2[1], nums2[2]] =&gt; [2,2,1]\n",
    "从下标 0 开始到下标 1 结束，形成了一个长度为 2 的非递减子数组 [2,2] 。 \n",
    "可以证明 2 是可达到的最大长度。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [1,3,2,1], nums2 = [2,2,3,4]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>构造 nums3 的方法之一是： \n",
    "nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] =&gt; [1,2,3,4]\n",
    "整个数组形成了一个长度为 4 的非递减子数组，并且是可达到的最大长度。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums1 = [1,1], nums2 = [2,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>构造 nums3 的方法之一是： \n",
    "nums3 = [nums1[0], nums1[1]] =&gt; [1,1] \n",
    "整个数组形成了一个长度为 2 的非递减子数组，并且是可达到的最大长度。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length == nums2.length == n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-non-decreasing-subarray-from-two-arrays](https://leetcode.cn/problems/longest-non-decreasing-subarray-from-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-non-decreasing-subarray-from-two-arrays](https://leetcode.cn/problems/longest-non-decreasing-subarray-from-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1]\\n[1,2,1]', '[1,3,2,1]\\n[2,2,3,4]', '[1,1]\\n[2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # we could alway choose smaller but make sure it's larger than previous\n",
    "        # do it for every index\n",
    "        longest = 1\n",
    "        @cache\n",
    "        def dp(i, prev_val):\n",
    "            nonlocal longest\n",
    "            if i == len(nums1):\n",
    "                return 0\n",
    "            opt1, opt2 = nums1[i], nums2[i]\n",
    "            ret = 0\n",
    "            for opt in [opt1, opt2]:\n",
    "                if opt >= prev_val:\n",
    "                    ret = max(ret, dp(i+1, opt) + 1)\n",
    "            temp = max(dp(i+1, -inf), dp(i+1, min(opt1, opt2)))\n",
    "            longest = max([longest, temp, ret])\n",
    "            return ret\n",
    "        dp(0, -inf)\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = f0 = f1 = 1\n",
    "        for (x0, y0), (x1, y1) in pairwise(zip(nums1, nums2)):\n",
    "            f = g = 1\n",
    "            if x0 <= x1: f = f0 + 1\n",
    "            if y0 <= x1: f = max(f, f1 + 1)\n",
    "            if x0 <= y1: g = f0 + 1\n",
    "            if y0 <= y1: g = max(g, f1 + 1)\n",
    "            f0, f1 = f, g\n",
    "            ans = max(ans, f0, f1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = deque(maxlen=2)\n",
    "        dp.append([1, 1])\n",
    "\n",
    "        n = len(nums1)\n",
    "        ans = 1\n",
    "        for i in range(1, n):\n",
    "            temp = [1, 1]\n",
    "            if nums1[i] >= nums1[i - 1]:\n",
    "                temp[0] = max(temp[0], dp[-1][0] + 1)\n",
    "            if nums1[i] >= nums2[i - 1]:\n",
    "                temp[0] = max(temp[0], dp[-1][1] + 1)\n",
    "            if nums2[i] >= nums2[i - 1]:\n",
    "                temp[1] = max(temp[1], dp[-1][1] + 1)\n",
    "            if nums2[i] >= nums1[i - 1]:\n",
    "                temp[1] = max(temp[1], dp[-1][0] + 1)\n",
    "            dp.append(temp)\n",
    "            ans = max(ans, max(temp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums=(nums1, nums2)\n",
    "        n=len(nums1)\n",
    "        dp=[[1]*n for _ in range(2)]\n",
    "        for i in range(1, n):\n",
    "            dp[0][i]=max(dp[0][i-1]+1 if nums1[i]>=nums1[i-1] else 1, \\\n",
    "                dp[1][i-1]+1 if nums1[i]>=nums2[i-1] else 1)\n",
    "            dp[1][i]=max(dp[0][i-1]+1 if nums2[i]>=nums1[i-1] else 1, \\\n",
    "                dp[1][i-1]+1 if nums2[i]>=nums2[i-1] else 1)\n",
    "        return max(max(dp[0]), max(dp[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        f1 = [1] * n\n",
    "        f2 = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if nums1[i] >= nums1[i - 1]:\n",
    "                f1[i] = max(f1[i], f1[i - 1] + 1)\n",
    "            if nums1[i] >= nums2[i - 1]:\n",
    "                f1[i] = max(f1[i], f2[i - 1] + 1)\n",
    "            if nums2[i] >= nums1[i - 1]:\n",
    "                f2[i] = max(f2[i], f1[i - 1] + 1)\n",
    "            if nums2[i] >= nums2[i - 1]:\n",
    "                f2[i] = max(f2[i], f2[i - 1] + 1)\n",
    "        return max(f1 + f2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = {}\n",
    "        dp[nums1[0]] = 1\n",
    "        dp[nums2[0]] = 1\n",
    "        ans = 1\n",
    "        for i in range(1, len(nums1)):\n",
    "            dp1, dp2 = dp[nums1[i-1]], dp[nums2[i-1]]\n",
    "            dp[nums1[i]] = 1\n",
    "            dp[nums2[i]] = 1\n",
    "            if nums1[i] >= nums1[i-1]:\n",
    "                dp[nums1[i]] = max(dp[nums1[i]], dp1 + 1)\n",
    "            if nums1[i] >= nums2[i-1]:\n",
    "                dp[nums1[i]] = max(dp[nums1[i]], dp2 + 1)\n",
    "            if nums2[i] >= nums1[i-1]:\n",
    "                dp[nums2[i]] = max(dp[nums2[i]], dp1 + 1)\n",
    "            if nums2[i] >= nums2[i-1]:\n",
    "                dp[nums2[i]] = max(dp[nums2[i]], dp2 + 1)\n",
    "            ans = max(ans, dp[nums2[i]], dp[nums1[i]])\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, n1: List[int], n2: List[int]) -> int:\n",
    "        a=[n1,n2]\n",
    "        n=len(a[0])\n",
    "        dp=[[1,1] for _ in range(n)]\n",
    "        #print(dp)\n",
    "        #dp[-1][0]=dp[-1][1]=1\n",
    "        ans=1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in (0,1):\n",
    "                for k in (0,1):\n",
    "                    if a[j][i]<=a[k][i+1]:\n",
    "                        dp[i][j]=max(dp[i][j],dp[i+1][k]+1)\n",
    "                        ans=max(ans,dp[i][j])\n",
    "        #print(dp)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # dp[i][0] 以nums1[i - 1]结尾的最长非递减子数组长度\n",
    "        res = 1\n",
    "        dp = [[1] * 2 for _ in range(len(nums1))]\n",
    "        for i in range(1, len(nums1)):\n",
    "            if nums1[i] >= nums1[i - 1] and nums1[i] >= nums2[i - 1]:\n",
    "                dp[i][0] = max(dp[i - 1][0] + 1, dp[i - 1][1] + 1)\n",
    "            elif nums1[i] >= nums1[i - 1] and nums1[i] < nums2[i - 1]:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "            elif nums1[i] < nums1[i - 1] and nums1[i] >= nums2[i - 1]:\n",
    "                dp[i][0] = dp[i - 1][1] + 1\n",
    "            else:\n",
    "                dp[i][0] = 1\n",
    "\n",
    "            if nums2[i] >= nums1[i - 1] and nums2[i] >= nums2[i - 1]:\n",
    "                dp[i][1] = max(dp[i - 1][0] + 1, dp[i - 1][1] + 1)\n",
    "            elif nums2[i] >= nums1[i - 1] and nums2[i] < nums2[i - 1]:\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "            elif nums2[i] < nums1[i - 1] and nums2[i] >= nums2[i - 1]:\n",
    "                dp[i][1] = dp[i - 1][1] + 1\n",
    "            else:\n",
    "                dp[i][1] = 1\n",
    "            \n",
    "            res = max(res, dp[i][0], dp[i][1])\n",
    "\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [[1,1,1] for _ in range(n)]\n",
    "        \"\"\"\n",
    "        dp[i][0]: store the maximum length\n",
    "        dp[i][1]: current length if store max\n",
    "        dp[i][2]: current length if store min\n",
    "        \"\"\"\n",
    "        for i in range(1,n):\n",
    "            n_1 = nums1[i]\n",
    "            n_2 = nums2[i]\n",
    "            high = max(n_1, n_2)\n",
    "            low = min(n_1, n_2)\n",
    "            if high >= max(nums1[i-1], nums2[i-1]):\n",
    "                dp[i][1] = max(dp[i-1][1:]) + 1\n",
    "            elif high >= min(nums1[i-1], nums2[i-1]):\n",
    "                dp[i][1] = dp[i-1][2] + 1\n",
    "            else:\n",
    "                dp[i][1] = 1\n",
    "            if low >= max(nums1[i-1], nums2[i-1]):\n",
    "                dp[i][2] = max(dp[i-1][1:]) + 1\n",
    "            elif low >= min(nums1[i-1], nums2[i-1]):\n",
    "                dp[i][2] = dp[i-1][2] + 1\n",
    "            else:\n",
    "                dp[i][2] = 1\n",
    "            dp[i][0] = max(max(dp[i][1:]), dp[i-1][0])\n",
    "        return dp[-1][0]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int],\n",
    "                               nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        @lru_cache(30)\n",
    "        def dp(i, pre):\n",
    "            if i < 0: return 0\n",
    "            return max(\n",
    "                dp(i - 1, nums1[i]) if nums1[i] <= pre else -1,\n",
    "                dp(i - 1, nums2[i]) if nums2[i] <= pre else -1\n",
    "            ) + 1\n",
    "\n",
    "        return max(dp(i, float('inf')) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        num_lens=[[nums1[i],nums2[i]]  for i in range(n)]\n",
    "        max_lens=[[1,1] for i in range(n)]\n",
    "        max_len=1\n",
    "        for i in range(1,n):\n",
    "\n",
    "            for k,ns in enumerate(num_lens[i]):\n",
    "                res=[max_lens[i-1][j]+1 if ns >=num_lens[i-1][j] else 1 for j in range(2)]\n",
    "                max_lens[i][k]=max(res)\n",
    "        for d in max_lens:\n",
    "            max_len=max(max_len,max(d))\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        num_lens=[[nums1[i],nums2[i]]  for i in range(n)]\n",
    "        max_lens=[[1,1] for i in range(n)]\n",
    "        max_len=1\n",
    "        for i in range(1,n):\n",
    "            for k,ns in enumerate(num_lens[i]):\n",
    "                res=max([max_lens[i-1][j]+1 if ns >=num_lens[i-1][j] else 1 for j in range(2)])\n",
    "                max_lens[i][k]=res\n",
    "                max_len = max(max_len, res)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int],\n",
    "                               nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        @lru_cache(n // 4)\n",
    "        def dp(i, pre):\n",
    "            if i < 0: return 0\n",
    "            return max(\n",
    "                dp(i - 1, nums1[i]) if nums1[i] <= pre else -1,\n",
    "                dp(i - 1, nums2[i]) if nums2[i] <= pre else -1\n",
    "            ) + 1\n",
    "\n",
    "        return max(dp(i, float('inf')) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        num, lens = [[-1 for _ in range(2)] for _ in range(n)], \\\n",
    "                    [[-1 for _ in range(2)] for _ in range(n)]\n",
    "        num[0] = [nums1[0], nums2[0]]\n",
    "        lens[0] = [1, 1]\n",
    "        ans = max(lens[0])\n",
    "        for i in range(1, n):\n",
    "            lens[i][0] = 1\n",
    "            num[i][0] = nums1[i]\n",
    "            if nums1[i] >= num[i - 1][0]:\n",
    "                lens[i][0] = max(lens[i][0], lens[i - 1][0] + 1)\n",
    "            if nums1[i] >= num[i - 1][1]:\n",
    "                lens[i][0] = max(lens[i][0], lens[i - 1][1] + 1)\n",
    "            #\n",
    "            lens[i][1] = 1\n",
    "            num[i][1] = nums2[i]\n",
    "            if nums2[i] >= num[i - 1][0]:\n",
    "                lens[i][1] = max(lens[i][1], lens[i - 1][0] + 1)\n",
    "            if nums2[i] >= num[i - 1][1]:\n",
    "                lens[i][1] = max(lens[i][1], lens[i - 1][1] + 1)\n",
    "            ans = max(ans, max(lens[i]))\n",
    "        print(lens)\n",
    "        return ans\n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp = [[0, 0] * 2 for _ in range(n)]\n",
    "        dp[0][0], dp[0][1] = [nums1[0], 1], [nums2[0], 1]\n",
    "        ans = 1\n",
    "        for i in range(1, n):\n",
    "            pre_0, pre_1 = dp[i-1][0], dp[i-1][1]\n",
    "            cur_0 = max(pre_0[1] + 1 if nums1[i] >= pre_0[0] else 1, pre_1[1] + 1 if nums1[i] >= pre_1[0] else 1)\n",
    "            dp[i][0] = [nums1[i], cur_0]\n",
    "            \n",
    "            cur_1 = max(pre_0[1] + 1 if nums2[i] >= pre_0[0] else 1, pre_1[1] + 1 if nums2[i] >= pre_1[0] else 1)\n",
    "            dp[i][1] = [nums2[i], cur_1]\n",
    "            ans = max(ans, cur_0, cur_1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        l=len(nums1)\n",
    "        if l==1: return 1\n",
    "        adj=[[] for i in range(l*2)]\n",
    "        \"\"\"\n",
    "        adj[2*i]=nums1[i],adj[2*i+1]=nums2[i]\n",
    "        \"\"\"\n",
    "        for i in range(l-1):\n",
    "            if nums1[i]<=nums1[i+1]:\n",
    "                adj[2*i].append(2*i+2)\n",
    "            if nums1[i]<=nums2[i+1]:\n",
    "                adj[2*i].append(2*i+3)\n",
    "            if nums2[i]<=nums1[i+1]:\n",
    "                adj[2*i+1].append(2*i+2)\n",
    "            if nums2[i]<=nums2[i+1]:\n",
    "                adj[2*i+1].append(2*i+3)\n",
    "        fin=[1]*(2*l)\n",
    "        for i in range(2*l):\n",
    "            for j in adj[i]:\n",
    "                fin[j]=max(fin[j],fin[i]+1)\n",
    "        return max(fin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = [[nums1[i], nums2[i]] for i in range(n)]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == 0 or min(nums[i-1]) > nums[i][j]:\n",
    "                return 1\n",
    "            else:\n",
    "                tmp = 0\n",
    "                if nums[i-1][0] <= nums[i][j]:\n",
    "                    tmp = 1 + dfs(i-1, 0)\n",
    "                if nums[i-1][1] <= nums[i][j]:\n",
    "                    tmp = max(tmp, 1 + dfs(i-1, 1))\n",
    "                return tmp\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i,0), dfs(i,1))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int],\n",
    "                               nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        @lru_cache(n // 2)\n",
    "        def dp(i, pre):\n",
    "            if i < 0: return 0\n",
    "            return max(\n",
    "                dp(i - 1, nums1[i]) if nums1[i] <= pre else -1,\n",
    "                dp(i - 1, nums2[i]) if nums2[i] <= pre else -1\n",
    "            ) + 1\n",
    "\n",
    "        return max(dp(i, float('inf')) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def dfs_f(i: int, x: int):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            y1 = dfs_f(i-1, nums1[i-1]) if nums1[i-1] <= x else 0\n",
    "            y2 = dfs_f(i-1, nums2[i-1]) if nums2[i-1] <= x else 0\n",
    "            return max(y1, y2) + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, dfs_f(i, nums1[i]), dfs_f(i, nums2[i]))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1);vis,ans=[[0]*n,[0]*n],0\n",
    "        nums=[nums1,nums2]\n",
    "        def dfs(u,v):\n",
    "            if(v+1==n):vis[u][v]=1;return 1\n",
    "            if(vis[u][v]):return vis[u][v]\n",
    "            vis[u][v]=1\n",
    "            if(nums[0][v+1]>=nums[u][v]):dfs(0,v+1);vis[u][v]=max(vis[u][v],vis[0][v+1]+1)\n",
    "            if(nums[1][v+1]>=nums[u][v]):dfs(1,v+1);vis[u][v]=max(vis[u][v],vis[1][v+1]+1)\n",
    "            return vis[u][v]\n",
    "        for i in range(n):ans=max(ans,dfs(0,i),dfs(1,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @cache\n",
    "        def mDFS(i, j):\n",
    "            if not i: return 1\n",
    "            res = 1\n",
    "            if nums1[i - 1] <= nums[j][i]:\n",
    "                res = mDFS(i - 1, 0) + 1\n",
    "            if nums2[i - 1] <= nums[j][i]:\n",
    "                res = max(res, mDFS(i - 1, 1) + 1)\n",
    "            return res\n",
    "        nums = [nums1, nums2]\n",
    "        return max(mDFS(i, j) for i in range(len(nums1)) for j in range(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums = (nums1, nums2)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if(i == 0):\n",
    "                return 1\n",
    "            res = 1\n",
    "            if nums[0][i-1] <= nums[j][i]:\n",
    "                res = max(res, dfs(i-1, 0) + 1)\n",
    "            if nums[1][i-1] <= nums[j][i]:\n",
    "                res = max(res, dfs(i-1, 1) + 1)\n",
    "            return res\n",
    "        for i in range(len(nums1)):\n",
    "            ans = max(ans, max(dfs(i, 0), dfs(i, 1)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i == 0: return 1\n",
    "            ans = 1\n",
    "            x = nums1[i] if j == 0 else nums2[i]\n",
    "            if nums1[i - 1] <= x:\n",
    "                ans = dfs(i - 1, 0) + 1\n",
    "            if nums2[i - 1] <= x:\n",
    "                ans = max(ans, dfs(i - 1, 1) + 1)\n",
    "            return ans\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            for j in range(2):\n",
    "                if j == 0:\n",
    "                    ans = max(ans, dfs(i, 0))\n",
    "                else:\n",
    "                    ans = max(ans, dfs(i, 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            res=1\n",
    "            nums=(nums1,nums2)\n",
    "            if nums1[i-1] <= nums[j][i]:\n",
    "                res=max(res,dfs(i-1,0)+1)\n",
    "            if nums2[i-1] <= nums[j][i]:\n",
    "                res=max(res,dfs(i-1,1)+1)\n",
    "            return res\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans=max(ans,dfs(i,0),dfs(i,1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        nums = (nums1, nums2)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0: return 1\n",
    "            ans = 1\n",
    "            if nums1[i - 1] <= nums[j][i]:\n",
    "                ans = dfs(i - 1, 0) + 1\n",
    "            if nums2[i - 1] <= nums[j][i]:\n",
    "                ans = max(ans, dfs(i - 1, 1) + 1)\n",
    "            return ans\n",
    "        return max(dfs(i, j) for j in range(2) for i in range(n))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
